Majority element [Boyer-Moore Majority Vote Algorithm]

Time: O(N); Space: O(1); easy

Given an array of size N, find the majority element. The majority element is the element that appears more than [N/2] times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: nums = [3,2,3]

Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]

Output: 2

class Solution1(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        idx, cnt = 0, 1

        for i in range(1, len(nums)):
            if nums[idx] == nums[i]:
                cnt += 1
            else:
                cnt -= 1
                if cnt == 0:
                    idx = i
                    cnt = 1

        return nums[idx]

s = Solution1()
nums = [3,2,3]
assert s.majorityElement(nums) == 3
nums = [2,2,1,1,1,2,2]
assert s.majorityElement(nums) == 2

import collections

class Solution2(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sorted(collections.Counter(nums).items(), key=lambda a: a[1], reverse=True)[0][0]

s = Solution2()
nums = [3,2,3]
assert s.majorityElement(nums) == 3
nums = [2,2,1,1,1,2,2]
assert s.majorityElement(nums) == 2

See also:

https://leetcode.com/problems/majority-element/